Cluster validation

We need to evaluate Clustering analysis (for Community structure, see Evaluation of community detection methods) methods. Because of the unsupervised nature, it is often harder to evaluate clustering methods.

The validation approaches can be categorized into three major ones: external evaluation, internal evaluation, and relative evaluation¹. The general criteria are compactness, connectedness, and separation. Compactness means that the members of a cluster should be close to each other. It is good to identify spherical clusters but may fail to detect connected clusters. Connectedness means that the members of a cluster should be very close to some other members of the cluster and the cluster should form connected set in the space. Separation indicates that two different clusters should be well-separated from each other.

External evaluation uses pre-classified items or gold standards to validate the clustering results. The results depend on the benchmark used and thus can have biases². The evaluation does not guarantee real-world performance.

Internal evaluation normally uses intra-group similarity vs. inter-group similarity.

Relative evaluation compares different methods or different parameters.

With information theory

• Information theory for cluster analysis

To read

• On Using Class-Labels in Evaluation of Clusterings
• A Review Of Monte Carlo Tests Of Cluster Analysis

References

• http://en.wikipedia.org/wiki/Cluster_analysis#Evaluation_of_Clustering_Results
• Adapting the Right Measures for K-means Clustering
• K-means Clustering versus Validation Measures: A Data Distribution Perspective